package com.czk.sort;

import java.util.Arrays;

/**
 * 插入排序
 *
 * @Author:ChenZhangKun
 * @Date: 2020/6/28 20:08
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] array = {2, 5, 8, 4, 6, 2, 1, 3, 9, 10, 15, 11, 7};
        // insertSort(array);
        insertSort_1(array);
    }

    public static void insertSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            // 从前一个开始索引，第一个本来就是有序
            int indexValue = i - 1;
            // 保存需要插入的值
            int value = array[i];
            // 循环的条件
            while (indexValue >= 0 && value < array[indexValue]) {
                // 将大的值往后推移
                array[indexValue + 1] = array[indexValue];
                indexValue--;
            }
            // 循环结束，将value插入到适当的位置
            array[indexValue + 1] = value;
        }
        System.out.println(Arrays.toString(array));
    }

    /**
     * 插入排序
     *
     * @param array
     */
    public static void insertSort_1(int[] array) {
        // 插入排序
        // 局部有序到全局有序
        for (int i = 1; i < array.length; i++) {
            for (int j = i; j > 0; j--) {
                if (array[j] < array[j - 1]) {
                    // 交换两个数字
                   /* int sum = array[j] + array[j - 1];
                    array[j] = sum - array[j];
                    array[j - 1] = sum - array[j - 1];*/
                    // 利用位异或运算进行交换
                    array[j] = array[j] ^ array[j - 1];
                    array[j - 1] = array[j] ^ array[j - 1];
                    array[j] = array[j] ^ array[j - 1];
                }

            }
            System.out.println(Arrays.toString(array));
        }
    }
}
